package com.example.heaptest;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

import static java.util.Collections.max;
import static java.util.Collections.swap;

/**
 * 堆的基本操作：https://www.hello-algo.com/chapter_heap/heap/
 */
public class Heap {
    List<Integer> max_heap;

    public Heap() {
        max_heap = new ArrayList<>();
    }

    /**
     * @param nums 初始化的列表，堆的初始化
     */
    public Heap(List<Integer> nums) {
        max_heap = new ArrayList<>(nums);
        for (int i = parent(nums.size() - 1); i >= 0; i--) {
            sitDown(i);
        }
    }

    int left(int i) {
        return 2 * i + 1;
    }

    int right(int i) {
        return 2 * i + 2;
    }

    int parent(int i) {
        return (i - 1) / 2;
    }

    // 访问堆顶元素
    int peek() {
        return this.max_heap.get(0);
    }

    // 元素入堆
    void push(int i) {
        max_heap.add(i);
        sitUp(max_heap.size() - 1);
    }


    /**
     * @param i ：i表示元素的位置，从i开始向上堆化
     */
    void sitUp(int i) {
        while (true) {
            int p = parent(i);
            if (parent(i) < 0 || max_heap.get(i) <= max_heap.get(p)) {  //已经到堆顶是，直接结束
                break;
            }
            swap(max_heap, i, p);
            i = p;
        }
    }

    /**
     * @return 当前堆顶元素
     */
    int pop() {
        if (max_heap.isEmpty()) {
            throw new IndexOutOfBoundsException();
        }
        swap(max_heap, 0, max_heap.size() - 1);

        int val = max_heap.remove(max_heap.size() - 1);
        sitDown(0);
        return val;
    }

    /**
     * @param i i代表当前位置
     */
    void sitDown(int i) {
        while (true) {
            int l = left(i);
            int r = right(i);
            int max_i = i;
            if (l <= max_heap.size() - 1 & max_heap.get(i) < max_heap.get(l)) {
                max_i = l;
            }
            if (r <= max_heap.size() - 1 & max_heap.get(i) < max_heap.get(r)) {
                max_i = r;
            }
            if (max_i == i) {
                break;
            }
            swap(max_heap, i, max_i);
            i = max_i;
        }
    }
}

class HeapSort {
    /**
     * 我们使用了与“堆”章节相同的从顶至底堆化 sift_down() 函数。值得注意的是，由于堆的长度会随着提取最大元素而减小，
     * 因此我们需要给 sift_down() 函数添加一个长度参数 n
     * ，用于指定堆的当前有效长度。代码如下所示：
     * n为当前堆的长度 i为元素开始下坠的位置
     */
    void sitDown(int[] nums, int n, int i) {
        int temp = 0;
        int my_index = i; //my_index记录记录i需要交换的位置
        while (true) {
            int l = 2 * i + 1;
            int r = 2 * i + 2;
            if (l <= n && nums[l] > nums[i]) {
                my_index = l;
            }
            if (r <= n && nums[r] > nums[i]) {
                my_index = r;
            }
            if (my_index == i) {
                break;
            }
            temp = nums[i];
            nums[i] = nums[my_index];
            nums[my_index] = temp;
            i = my_index;  // 更新当前节点交换后的位置
        }
    }

    void heapSort(int[] nums) {
        // 先建堆
        for (int i = (nums.length - 1) / 2; i >= 0; i--) {
            sitDown(nums, nums.length - 1, i);
        }
        // 出堆n次，每次长度-1
        for (int i = nums.length - 1; i > 1; i--) {
            int temp = nums[i];
            nums[i] = nums[0];
            nums[0] = temp;
            sitDown(nums, i, 0);
        }
    }
}
